package com.rgs.se.algorithm.daywork;

public class Maxsublist {

    public static void main(String[] args) {
        int[] arr = {2,1,5,3,6,4,8,9,7};
        int[] dp = getdp(arr);          //该数组存放对应arr[i]为末尾的最长子序列
        int[] lis = getLIS(arr,dp);
        System.out.print("最长单调递增子序列为:");
        for (int i = 0; i < lis.length; i++) {
            System.out.print(lis[i]+",");
        }
    }

    public static int[] getdp(int[] arr){
        int[] dp = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            dp[i] = 1;
            for (int j = 0; j < i; j++){
                if (arr[j] < arr[i]){
                    dp[i] = max(dp[j]+ 1, dp[i]);
                }
            }
        }
        return dp;
    }
    //找到最长子序列的长度
    public static int[] getLIS(int[] arr,int[] dp){
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) { //寻最长递增子序列末尾的位置和值
            if (dp[i] > len) {
                len = dp[i];              // 最长序列长度
                index = i;                // 最长序列末位置
            }
        }
        //各个元素的位置
        int[] lis = new int[len];
        lis[--len] = arr[index];
        for (int i = index; i >= 0; i--){
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1){  //从后往前找子序列
                lis[--len] = arr[i];
                index = i;
            }
        }
        return lis;
    }

    public static int max(int a,int b){
        if(a >= b){
            return a;
        }
        else return b;
    }

}
